package 回溯;

public class Queen3 {
	
	private int[] queen;
	private byte cols;
	private short leftTop;
	private short rightTop;
	private int ways;
	
	public static void main(String[] args) {
		new Queen3().placeNQueen();
	}
	
	public void placeNQueen() {
		queen = new int[8];
		place(0);
	}
	
	public void place(int row) {
		if (row == 8) {
			ways++;
			show();
			System.out.println(ways);
			return;
		}
		for (int col = 0; col < 8; col++) {
			int cv = 1 << col;
			if ((cv & cols) != 0) continue;
			int lv = 1 << row - col + 7;
			if ((lv & leftTop) != 0) continue;
			int rv = 1 << row + col;
			if ((rv & rightTop) != 0) continue;
			
			queen[row] = col;
			cols |= cv;
			leftTop |= lv;
			rightTop |= rv;
			place(row + 1);
			cols &= ~cv;
			leftTop &= ~lv;
			rightTop &= ~rv;
			
		}
	}
	
	public void show() {
		for (int i = 0; i < queen.length; i++) {
			for (int j = 0; j < queen.length; j++) {
				if (queen[i] == j) {
					System.out.print("1 ");
				} else {
					System.out.print("0 ");
				}
			}
			System.out.println();
		}
	}
}
